[Coding044] LeetCode 150

Evaluate Reverse Polish Notation

More coding records

Get the knowledge flowing and circulating! :)

目录

※ 本题收获

• 逆波兰表达式

• switch用法复习

• String变Integer

• 字符串判等

题目：150. Evaluate Reverse Polish Notation

You are given an array of strings tokens that represents an arithmetic expression in a Reverse Polish Notation.

Evaluate the expression. Return an integer that represents the value of the expression.

Note that:

• The valid operators are '+', '-', '*', and '/'.

• Each operand may be an integer or another expression.

• The division between two integers always truncates toward zero.

• There will not be any division by zero.

• The input represents a valid arithmetic expression in a reverse polish notation.

• The answer and all the intermediate calculations can be represented in a 32-bit integer.

Example 1:

xxxxxxxxxx
3
1
Input: tokens = ["2","1","+","3","*"]
2
Output: 9
3
Explanation: ((2 + 1) * 3) = 9

Example 2:

xxxxxxxxxx
3
1
Input: tokens = ["4","13","5","/","+"]
2
Output: 6
3
Explanation: (4 + (13 / 5)) = 6

Example 3:

xxxxxxxxxx
9
1
Input: tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
2
Output: 22
3
Explanation: ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
4
= ((10 * (6 / (12 * -11))) + 17) + 5
5
= ((10 * (6 / -132)) + 17) + 5
6
= ((10 * 0) + 17) + 5
7
= (0 + 17) + 5
8
= 17 + 5
9
= 22

Constraints:

• 1 <= tokens.length <= 104

• tokens[i] is either an operator: "+", "-", "*", or "/", or an integer in the range [-200, 200].

代码1（配 · 手绘过程图）

xxxxxxxxxx
50
1
class Solution {
2
    public int evalRPN(String[] tokens) {
3
        Stack<Integer> stack = new Stack();
4

5
        int op1 = 0;
6
        int op2 = 0;
7

8
        for (String each : tokens)
9
        {
10
            switch(each)
11
            {
12
                case "+":
13
                    {
14
                        op2 = stack.pop();
15
                        op1 = stack.pop();
16
                        stack.push(op1 + op2);
17
                    }
18
                    break;
19
                case "-":
20
                    {
21
                        op2 = stack.pop();
22
                        op1 = stack.pop();
23
                        stack.push(op1 - op2);
24
                    }
25
                    break;
26
                case "*":
27
                    {
28
                        op2 = stack.pop();
29
                        op1 = stack.pop();
30
                        stack.push(op1 * op2);
31
                    }
32
                    break;
33
                case "/":
34
                    {
35
                        op2 = stack.pop();
36
                        op1 = stack.pop();
37
                        stack.push(op1 / op2);
38
                    }
39
                    break;
40
                default:
41
                {
42
                    stack.push(Integer.parseInt(each));
43
                }                
44

45
            }
46
        }
47

48
        return stack.pop();
49
    }
50
}

代码解读 | 评价

思路清晰之后，写出来的代码就比较可观了！

• op1 - op2

• op1 / op2

注意顺序：栈中弹出的第一数是op2, 第2个数是op1。这个对于加法、乘法没有影响，但是对于减法和除法有影响。

代码2（以前写的代码）

xxxxxxxxxx
53
1
class Solution {
2
    public int evalRPN(String[] tokens) {
3
        // 定义一个整数栈（Integer）
4
        Stack<Integer> st = new Stack<>();
5
        
6
        // 问题1： 怎样把字符串“12”变成int型呢？
7
        // 解答：
8
        // ① Integer.valueOf(string)
9
        // ② Integer.parseInt(string)
10
        
11
        int a = Integer.valueOf(tokens[0]);
12
        System.out.println(a + 1);
13
        
14
        // 问题2：怎样对比两个字符串呢？
15
        // 解答：str1.equals(".")  or  !str1.equals(".")
16
        
17
        System.out.println(tokens[2].equals("+"));
18
        
19
        // coding here
20
        for (String s : tokens)
21
        {
22
            if (!s.equals("+") && !s.equals("-") && !s.equals("*") && !s.equals("/"))
23
            {
24
                st.push(Integer.parseInt(s));
25
            }
26
            else
27
            {
28
                int num2 = st.pop();
29
                int num1 = st.pop();
30
                int res = 0;
31
                switch(s)
32
                {
33
                    case "+":
34
                        res = num1 + num2;
35
                        break;
36
                    case "-":
37
                        res = num1 - num2;
38
                        break;
39
                    case "*":
40
                        res = num1 * num2;
41
                        break;
42
                    case "/":
43
                        res = num1 / num2;
44
                        break;
45
                }
46
                st.push(res);
47
            }
48
        }
49
        
50
        return st.pop();
51
    }
52
}
53

代码解读 | 评价

• 以前写的代码似乎看上去有点复杂呢~

★ 知识点积累 (Java)

// 问题1： 怎样把字符串“12”变成int型呢？

xxxxxxxxxx
3
1
// 解答：
2
Integer.valueOf(string)
3
Integer.parseInt(string)

// // 问题2：怎样对比两个字符串呢？

xxxxxxxxxx
3
1
// 解答：
2
str1.equals(".")  
3
!str1.equals(".")